package woa.linkedlist;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wangpeng
 * @version 1.0
 * @date 2024/2/22 19:09
 */
public class LRUCache {

    private int capacity;
    private int size;
    private Map<Integer, DLinkedNode> map = new HashMap<Integer, DLinkedNode>();
    private DLinkedNode head = null, tail = null;

    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            DLinkedNode target = map.get(key);
            if (target.prev != null) {
                target.prev.next = target.next;
                target.next = head;
                if (tail == target) {
                    tail = target.prev;
                }
                target.prev.prev = target;
                target.prev = null;
                head = target;
            }
            return target.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            DLinkedNode target = map.get(key);
            target.value = value;
            return;
        }

        DLinkedNode node = new DLinkedNode(key, value);
        node.next = head;
        if (head != null) {
            head.prev = node;
        }
        head = node;
        if (tail == null) tail = node;
        size++;
        map.put(key, node);
        if (size > capacity) {
            map.remove(tail.key);
            if (tail.prev != null) {
                tail.prev.next = null;
            }
            tail = tail.prev;
            if (tail == null) {
                head = null;
            }
            size--;
        }
    }

    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        lRUCache.get(1);    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        lRUCache.get(2);    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        lRUCache.get(1);    // 返回 -1 (未找到)
        lRUCache.get(3);    // 返回 3
        lRUCache.get(4);    // 返回 4
    }
}
